package yifeng.program;

import yifeng.program.utils.Utils;

public class Test {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int m =100;
		while(m-- > 0){
			int[] a = Utils.createIntArray(10, 1, 100);
			
			printArray(a);
			
			
//			int i = 0, j = 0;
//			for(;i < a.length; i++)
//				for(j = 0; j < a.length-i-1; j++){
//					if(a[j] > a[j+1])
//						swap(a, j, j+1);
//				}
			quickSort(a, 0, a.length-1);
			
			System.out.println("After sorting:");
			printArray(a);
			System.out.println();
		}
	}
	
	
	
	public static void quickSort(int[] a, int start, int end){
		if(start >= end) 
			return;
		
		int index = partition(a, start, end);
		quickSort(a, start, index-1);
		quickSort(a, index+1, end);
	}



	private static int partition(int[] a, int start, int end) {
		int i = start + 1;
		int j = end;
		
		while(true){
			if(i == j){
				if(a[i] <= a[start]){
					swap(a, i, start);
					return i;
				}
				else if(a[i] > a[start]){
					swap(a, i-1, start);
					return i-1;
				}
			}
			
			
			if(a[i] <= a[start]) 
				i++;
			else if(a[i] > a[start])
				swap(a, i, j--);
		}		
	}



	private static void swap(int[] a, int i, int j) {
		int temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}
	
	private static void printArray(int[] a){
		int i = 0;
		for(; i < a.length-1; i++){
			System.out.print(a[i] + "-");
		}
		System.out.println(a[i]);
	}

}
